package com.lgc.algorithm.quick;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {3,2};//{3, 23, 9, 0, 87, 6, 2, 212, 0, 9, 6};

        printArray(numbers);
        quickSort(numbers, 0, numbers.length - 1);

        System.out.println("==================");
        printArray(numbers);
    }

    static void printArray(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i]);
        }
    }

    public static void quickSort(int[] numbers, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            // 找中位间数索引（一般以数组的第一个数作标杆）
            int middleIndex = getMiddleIndex(numbers, startIndex, endIndex);

            //对低字段表进行递归排序
            quickSort(numbers, startIndex, middleIndex - 1);
            //对高字段表进行递归排序
            quickSort(numbers, middleIndex + 1, endIndex);
        }
    }

    // 以数组的第一个数作标杆,进行一次排列，并返回标杆数排列后所在的位置（将小于标杆的数放在它左边，奖大于标杆的数放在它右边）
    public static int getMiddleIndex(int[] numbers, int startIndex, int endIndex) {
        int flagValue = numbers[startIndex];
        int flagIndex = startIndex;
        while (startIndex < endIndex) {
            while (startIndex < endIndex && numbers[flagIndex] <= numbers[endIndex]) {
                endIndex--;
            }
            numbers[flagIndex] = numbers[endIndex];
            numbers[endIndex] = flagValue;
            flagIndex = endIndex;

            while (startIndex < endIndex && numbers[startIndex] <= numbers[flagIndex]) {
                startIndex++;
            }
            numbers[flagIndex] = numbers[startIndex];
            numbers[startIndex] = flagValue;
            flagIndex = startIndex;
        }

        return flagIndex;
    }
}




